<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3672：[Noi2014]购票</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Noi2014]购票</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Noi2014]购票</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Noi2014]购票                </h1>
                <p>时间限制：30s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：512MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div><span style="font-size: 16px">&nbsp;今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。</span></div>
<div><span style="font-size: 16px">&nbsp; &nbsp; &nbsp; &nbsp;全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的</span><span style="font-size: 16px"> </span><span style="font-size: 16px">n</span><span style="font-size: 16px"> </span><span style="font-size: 16px">个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 </span><span style="font-size: 16px">v</span><span style="font-size: 16px">，我们给出了它在这棵树上的父亲城市 f</span><sub><span style="font-size: 16px">v</span></sub><span style="font-size: 16px"> &nbsp;以及到父亲城市道路的长度 s</span><sub><span style="font-size: 16px">v</span></sub><span style="font-size: 16px">。</span></div>
<div><span style="font-size: 16px">从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。</span></div>
<div><span style="font-size: 16px">对于任意一个城市 v，我们会给出一个交通工具的距离限制 l</span><sub><span style="font-size: 16px">v</span></sub><span style="font-size: 16px">。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 l</span><sub><span style="font-size: 16px">v</span></sub><span style="font-size: 16px"> &nbsp;时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 p</span><sub><span style="font-size: 16px">v</span></sub><span style="font-size: 16px">,q</span><sub><span style="font-size: 16px">v</span></sub><span style="font-size: 16px"> &nbsp;作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dp<sub>v</sub>+q<sub>v</sub>。</span></div>
<div><span style="font-size: 16px">每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。</span></div>
<div></div></p><hr/><h3>输入格式</h3><p><p><span style="font-size: medium">第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n 行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2 到城市 n。 </span></p></p><hr/><h3>输出格式</h3><p><p><span style="font-size: medium">输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。 </span></p>
<p class="MsoNormal"><span style="font-size: medium"><span lang="EN-US">&nbsp;</span></span></p></p><hr/><h3>样例输入</h3><pre>7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10
</pre><hr/><h3>样例输出</h3><pre> 
40
150
70
149
300
150 </pre><hr/><h3>提示</h3><p><p>
<p></p>
<p>&nbsp;</p>
<p></p>
</p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun"><img height="696" alt="" width="732" src="../file/3672_0.jpg" /></span></span></p>
<p class="NOI"></p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun">对于所有测试数据，保证 0&le;p<sub>v</sub>&le;10<sup>6</sup>，0&le;q<sub>v</sub>&le;10<sup>12</sup>，1&le;f<sub>v</sub>&lt;v；保证 0&lt;s<sub>v</sub>&le;l<sub>v</sub>&le;2&times;10<sup>11</sup>，且任意城市到SZ市的总路程长度不超过 2&times;10<sup>11</sup>。</span></span></p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun">输入的 t 表示数据类型，0&le;t&lt;4，其中：</span></span></p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun">当 t=0 或 2 时，对输入的所有城市 v，都有 f<sub>v</sub>=v-1，即所有城市构成一个以SZ市为终点的链；</span></span></p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun">当 t=0 或 1 时，对输入的所有城市 v，都有 l<sub>v</sub>=2&times;10<sup>11</sup>，即没有移动的距离限制，每个城市都能到达它的所有祖先；</span></span></p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun">当 t=3 时，数据没有特殊性质。</span></span></p>
<p class="NOI"><span style="font-family: 黑体"><span style="font-size: 16px; font-family: SimSun">n=2&times;10^5</span></span></p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3672" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3672" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>